public class test {
    //leetcode 面试题17.16.按摩师
    class Solution {
        public int massage(int[] nums) {
            // 1. 创建dp[][]表
            int n = nums.length;
            if(n == 0){
                return 0;
            }
            //代表接受i号的预约时,最大的休息时间
            int[] f = new int[n];
            //不接受i号预约时,最大的休息时间
            int[] g = new int[n];
            // 2. 初始化
            f[0] = nums[0];
            // 3. 填表
            for(int i = 1;i < n;i++){
                f[i] = g[i - 1] + nums[i];//要求不相邻预约,则由上个未预约的最大值为基本
                g[i] = Math.max(g[i - 1],f[i - 1]);
            }
            // 4. 返回值
            return Math.max(f[n-1],g[n-1]);
        }
    }
    //leetcode 198.打家劫舍
    class Solution {
        public int rob(int[] nums) {
            // 1. 创建dp[]表
            int n = nums.length;
            int[] f = new int[n];
            int[] g = new int[n];
            // 2. 初始化
            f[0] = nums[0];
            // 3. 填表
            for(int i = 1;i < n;i++){
                f[i] = g[i - 1] + nums[i];
                g[i] = Math.max(f[i - 1],g[i - 1]);
            }
            // 4. 返回值
            return Math.max(f[n-1],g[n-1]);
        }
    }
    //leetcode 740.删除并获得点数
    class Solution {
        public int deleteAndEarn(int[] nums) {
            //模拟(打家劫舍)问题,利用计数排序将数组排序
            //这样(删除相邻项)就变成了(不能访问相邻元素)时能得到的最大点数
            int n = nums.length;
            int max = 0;
            for(int i = 0;i < n;i++){
                max = Math.max(nums[i],max);
            }
            int[] arr = new int[max+1];
            for(int i = 0;i < n;i++){
                arr[nums[i]] += nums[i];
            }
            int[] dp = new int[max+1];
            dp[0] = arr[0];
            dp[1] = Math.max(arr[0],arr[1]);
            for(int i = 2;i <= max;i++){
                dp[i] = Math.max(dp[i - 1],dp[i - 2] + arr[i]);
            }
            return dp[max];
        }
    }
    //leetcode 213.打家劫舍Ⅱ
    class Solution {
        public int rob(int[] nums) {
            // 1. 创建dp[]表
            int n = nums.length;
            int[] f = new int[n];
            int[] g = new int[n];
            boolean flg = false;
            // 2. 初始化
            // 计算偷第一家
            f[0] = nums[0];
            if(n == 1){
                return nums[0];
            }
            // 3. 填表
            for(int i = 1;i < n;i++){
                f[i] = g[i - 1] + nums[i];
                g[i] = Math.max(g[i - 1],f[i - 1]);
            }
            int n1 = Math.max(f[n - 2],g[n - 1]);
            // 计算不偷第一家
            f[0] = 0;
            g[0] = 0;
            for(int i = 1;i < n;i++){
                f[i] = g[i - 1] + nums[i];
                g[i] = Math.max(g[i - 1],f[i - 1]);
            }
            int n2 = Math.max(f[n - 1],g[n - 1]);
            // 4. 返回值
            return Math.max(n1,n2);
        }
    }
}
